
<!DOCTYPE html>
<!--[if IEMobile 7 ]><html class="no-js iem7"><![endif]-->
<!--[if lt IE 9]><html class="no-js lte-ie8"><![endif]-->
<!--[if (gt IE 8)|(gt IEMobile 7)|!(IEMobile)|!(IE)]><!--><html class="no-js" lang="en"><!--<![endif]-->
<head>
  <meta charset="utf-8">
  <title>深入解析Bloom Filter(上) - Yebangyu's Blog</title>
  <meta name="author" content="Yebangyu">

  
  <meta name="description" content="本文介绍了Bloom Filter、Counting Bloom Filter等知识">
  <meta name="keywords" content="Bloom Filter Counting Bloom Filter">

  <!-- http://t.co/dKP3o1e -->
  <meta name="HandheldFriendly" content="True">
  <meta name="MobileOptimized" content="320">
  <meta name="viewport" content="width=device-width, initial-scale=1">

  
  <link rel="canonical" href="http://www.yebangyu.org/blog/2016/01/23/insidethebloomfilter/">
  <link href="/favicon.png" rel="icon">
  <link href="/stylesheets/screen.css" media="screen, projection" rel="stylesheet" type="text/css">
  <link href="/atom.xml" rel="alternate" title="Yebangyu's Blog" type="application/atom+xml">
  <script src="/javascripts/modernizr-2.0.js"></script>
  <script src="//ajax.lug.ustc.edu.cn/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
  <script>!window.jQuery && document.write(unescape('%3Cscript src="/javascripts/libs/jquery.min.js"%3E%3C/script%3E'))</script>
  <script src="/javascripts/octopress.js" type="text/javascript"></script>
  <!--Fonts from Google"s Web font directory at http://google.com/webfonts -->
<link href="//fonts.lug.ustc.edu.cn/css?family=PT+Serif:regular,italic,bold,bolditalic" rel="stylesheet" type="text/css">
<link href="//fonts.lug.ustc.edu.cn/css?family=PT+Sans:regular,italic,bold,bolditalic" rel="stylesheet" type="text/css">
<!-- mathjax config similar to math.stackexchange -->
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
  jax: ["input/TeX", "output/HTML-CSS"],
  tex2jax: {
    inlineMath: [ ['$', '$'] ],
    displayMath: [ ['$$', '$$']],
    processEscapes: true,
    skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
  },
  messageStyle: "none",
  "HTML-CSS": { preferredFont: "TeX", availableFonts: ["STIX","TeX"] }
});
</script>
<script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML" type="text/javascript"></script>

  

</head>

<body   >
  <header role="banner"><hgroup>
  <h1><a href="/">Yebangyu's Blog</a></h1>
  
    <h2>Fond of Concurrency Programming and Machine Learning</h2>
  
</hgroup>

</header>
  <nav role="navigation"><ul class="subscription" data-subscription="rss">
  <li><a href="/atom.xml" rel="subscribe-rss" title="subscribe via RSS">RSS</a></li>
  
</ul>
  
<form action="https://www.google.com/search" method="get">
  <fieldset role="search">
    <input type="hidden" name="sitesearch" value="www.yebangyu.org">
    <input class="search" type="text" name="q" results="0" placeholder="Search"/>
  </fieldset>
</form>
  
<ul class="main-navigation">
  <li><a href="/">Blog</a></li>
  <li><a href="/blog/archives">Archives</a></li>
  <li><a href="/about">About Me</a></li>
</ul>

</nav>
  <div id="main">
    <div id="content">
      <div>
<article class="hentry" role="article">
  
  <header>
    
      <h1 class="entry-title">深入解析Bloom Filter(上)</h1>
    
    
      <p class="meta">
        




<time class='entry-date' datetime='2016-01-23T13:24:49+08:00'><span class='date'><span class='date-month'>Jan</span> <span class='date-day'>23</span><span class='date-suffix'>rd</span>, <span class='date-year'>2016</span></span> <span class='time'>1:24 pm</span></time>
        
      </p>
    
  </header>


<div class="entry-content"><p>本文将介绍：</p>

<blockquote>
  <ul>
    <li>Bloom Filter和它的变形与拓展</li>
    <li>Bloom Filter的使用场景</li>
    <li>Bloom Filter的详细数学分析</li>
  </ul>
</blockquote>

<h2 id="section">提出问题</h2>

<p>Google的爬虫每天需要抓取大量的网页。于是就有一个问题：每当爬虫分析出一个url的时候，是抓呢，还是不抓呢？如何知道这个url已经爬过了？</p>

<!--more-->

<p>这个问题，归纳抽象后可以定义为：</p>

<p>给定一个集合S（注意，这里的集合是传统意义上的集合：元素彼此不同。本文不考虑multiset），给定一个元素e，需要判断$e\in S$ 是否成立。（学术界一般称为membership问题）</p>

<h2 id="section-1">分析问题</h2>

<p>都有哪些方案可以解决这个问题？</p>

<p>一种简单的想法是把url存储在一个哈希表中，每次去表里look up下判断是否存在。假如每个url占用40B，那么10亿条url将占用大概30多GB的内存！Can this be more space efficient ?</p>

<h2 id="section-2">解决问题</h2>

<p>我们可不可以不存url本身？这样子所需空间就会大大减少了。于是我们想到一个很经典的做法：bitmap（位图）。将集合S中的url哈希到bitmap上，给定一个url，只需要将它hash，得到它在bitmap的下标，检查该位置是否为1即可。</p>

<p>这样做空间是省了，可是也产生了一个问题：由于冲突（碰撞），不是集合S中的元素也可能被哈希到值为1的位置上，导致误报。</p>

<p>给定一个元素e，如果实际上$e\notin S$ 而被判为 $e\in S$，那么我们称e是false positive（伪正例。顺便说一句，false positive等的分析在machine learning的classification任务里评价model时非常重要）。</p>

<p>如何降低false positive的概率呢？Bloom Filter的想法是使用多个独立的哈希函数。</p>

<h3 id="standard-bloom-filter">Standard Bloom Filter</h3>

<p>在传统的Bloom Filter中，我们有：</p>

<p>集合S：其大小为m。也就是说，集合中有m个不同元素。</p>

<p>可用内存B：B被当成位数组bitmap来使用，大小为n。（有n个bit）。</p>

<p>哈希函数：有k个独立的、均匀分布的哈希函数。</p>

<p>Bloom Filter的做法是：初始时，所有比特位都初始化为0。对于集合中的每个元素，利用k个哈希函数，对它哈希得到k个位置，将bitmap中的对应的k个位置置为1。</p>

<p>给定一个元素e，为了判断它是否是集合中的元素，也利用该k个函数得到k个位置，检查该k个位置是否都为1，如果是，认为$e\in S$，否则认为$e\notin S$。</p>

<p>不难看出，如果$e\in S$，那么Bloom Filter肯定会正确判断出$e\in S$，但是它还是可能产生false positive。那么，如何分析false positive的概率呢？</p>

<p>false positive发生时，表示哈希该元素后得到的k个位置都为1。这个概率大概为：</p>

<p>$P\approx p_1^k$</p>

<p>其中$p_1$代表某位为1的概率，它等于：</p>

<p>$p_1 = 1 - p_0$</p>

<p>对于$p_0$，表示某个特定的比特位为0。什么时候该位才为0呢？也就是说m个元素各自经过k次哈希得到km个对象，没有一个对象定位到了该位置。某个对象定位到该位置的概率为$\frac{1}{n}$，因此我们可以得到：</p>

<p>$p_0 = (1 - \frac{1}{n})^{mk}$</p>

<p>分析$p_0$。在实际应用中，n一般很大，根据重要极限公式，我们有：</p>

<p>$p_0 = (1 - \frac{1}{n})^{mk} = (1-\frac{1}{n})^{-n{\frac{mk}{-n}}} \approx e^{-\frac{mk}{n}} $</p>

<p>代入到最上面的那个式子，我们不难得到：</p>

<p>$P \approx ({1 - e^{-\frac{mk}{n}}})^{k}$</p>

<p>当k为何值时，P取得最小，false positive possibility最低呢？</p>

<p>令 $f(k) = ({1 - e^{-\frac{mk}{n}}})^{k}$</p>

<p>$ln(f(k)) = kln({1 - e^{-\frac{mk}{n}}})$</p>

<p>$\frac{f\prime(k)}{f(k)} = ln({1 - e^{-\frac{mk}{n}}}) + k(\frac{1}{1 - e^{- \frac{mk}{n}}})(- e^{-\frac{mk}{n}})(\frac{-m}{n})$</p>

<p>$f\prime(k) = f(k)(ln({1 - e^{-\frac{mk}{n}}}) + k(\frac{1}{1 - e^{- \frac{mk}{n}}})(- e^{-\frac{mk}{n}})(\frac{-m}{n}))$</p>

<p>看起来够复杂了，然而别怕！！！</p>

<p>令$f\prime(k) = 0$ ， 我们有(注意到$f(k) &gt; 0$ 恒成立)：</p>

<p>$ln({1 - e^{-\frac{mk}{n}}}) + k(\frac{1}{1 - e^{- \frac{mk}{n}}})(- e^{- \frac{mk}{n}})(\frac{-m}{n}) = 0$</p>

<p>作代换，令$\lambda = e^{-\frac{mk}{n}}$ 则 $k = \frac{-nln\lambda}{m}$，代入上式，得到</p>

<p>$(1-\lambda)ln(1-\lambda) = \lambda ln\lambda$</p>

<p>因此$\lambda = \frac{1}{2}$ ， $k = \frac{n}{m}ln2$</p>

<p>也就是说，当n和m固定时，选择$k = \frac{n}{m}ln2$ 附近的一个整数，将使false positive possibility最小。</p>

<p>工程实现时，我们需要k个哈希函数或者哈希函数值。如何构造和获得k个独立的哈希函数呢？这篇<a href="https://www.eecs.harvard.edu/~michaelm/postscripts/rsa2008.pdf">论文</a> 提出，只需要两个独立的哈希函数hf1和hf2即可，也就是通过如下方式获得k个哈希函数值：</p>

<p>hash value = hf1(key) + i*hf2(key)</p>

<p>其中i=0、1、2…k-1</p>

<h3 id="counting-bloom-filter">Counting Bloom Filter</h3>

<p>除了存在false positive这个问题之外，传统的Bloom Filter还有一个不足：无法支持删除操作（想想看，是不是这样的）。而Counting Bloom Filter(CBF)就是用来解决这个问题的。</p>

<p>在CBF中，维护的不是单纯的标示0或者1的比特位，而是计数器counter。对于集合中的每个元素，利用k个哈希函数，对它哈希得到k个位置，将对应的k个位置上的k个counter都加1。删除时，只需要把k个counter都减1即可。</p>

<p>那么，这个counter应该占用几位呢？分配太多，浪费空间；分配太少，容易溢出。通过下面的分析，我们可以知道，实际使用时，4位足矣。</p>

<p>考察（是考察，不是考查。这两个词有什么区别？）某个位置，该位置的计数器counter的值$\xi$</p>

<p>$P(\xi = c) \approx \binom{mk}{c} {(\frac{1}{n})}^{c}({1-\frac{1}{n}})^{mk-c} = B(km,\frac{1}{n})$</p>

<p>这个式子有点点复杂，然而回忆下概率论里的知识：若二项分布B(n,p)里n很大，p很小时，二项分布的极限近似分布是泊松分布$P(\lambda=k) = \frac{\lambda^k}{k!}{e}^{-\lambda}$，其中$\lambda=np$，因此：</p>

<p>$P(\xi = c) \approx \binom{mk}{c} {(\frac{1}{n})}^{c}({1-\frac{1}{n}})^{mk-c} \approx \frac{({\frac{km}{n}})^{c}}{c!}{e}^{-{\frac{km}{n}}}$</p>

<p>令$k = \frac{n}{m}ln2$，代入，我们得到</p>

<p>$P(\xi &gt;16) \approx \frac{(ln2)^{16}}{16!} * \frac{1}{2} &lt; \frac{1}{16!} = \frac{1}{20922789888000}$</p>

<p>也就是说，选择4位来存counter在实际情况中已经足矣，发生溢出的概率极小。</p>

<h2 id="section-3">本文小结</h2>

<p>总结下，Bloom Filter可以用在什么地方，或者说，在什么场景下，你应该想到这种技术：</p>

<p>1，回答是或者不是的问题。你需要判断一个元素是否属于某个集合，仅仅这样。你不应该要求更多。如果你想获得该元素对应的value或者还有其他payload，那么bloom filter不适合你，你需要哈希表。</p>

<p>2，允许false positive。也就是说，发生false positive不应该是致命的。比如说，搜索引擎的爬虫里，如果url不是set的元素，却被bloom filter过滤了，那么顶多就是不抓它而已，没啥特别大的损失。</p>

<p>3，空间敏感。作为一种概率数据结构，Bloom Filter不存储原始数据（比如说url），这也是它为什么space efficient的本质原因。</p>

<p>有了Standard Bloom Filter和Counting Bloom Filter，似乎可以满足绝大多数需求了，然而，这里面还是有问题。什么问题？请看<a href="http://www.yebangyu.org/blog/2016/01/29/insidethebloomfilter/">下集</a>。</p>
</div>


  <footer>
    <p class="meta">
      
  

<span class="byline author vcard">Posted by <span class="fn">Yebangyu</span></span>

      




<time class='entry-date' datetime='2016-01-23T13:24:49+08:00'><span class='date'><span class='date-month'>Jan</span> <span class='date-day'>23</span><span class='date-suffix'>rd</span>, <span class='date-year'>2016</span></span> <span class='time'>1:24 pm</span></time>
      

<span class="categories">
  
    <a class='category' href='/blog/categories/suan-fa/'>算法</a>
  
</span>


    </p>
    
      <div class="sharing">
  
  
  
</div>

    
    <p class="meta">
      
        <a class="basic-alignment left" href="/blog/2016/01/17/concurrenyandparallism/" title="Previous Post: Concurrent and Parallel">&laquo; Concurrent and Parallel</a>
      
      
        <a class="basic-alignment right" href="/blog/2016/01/24/spinlock-and-mutex/" title="Next Post: Spinlock and mutex">Spinlock and mutex &raquo;</a>
      
    </p>
  </footer>
</article>


</div>

<aside class="sidebar">
  
    <section>
  <h1>Recent Posts</h1>
  <ul id="recent_posts">
    
      <li class="post">
        <a href="/blog/2017/03/11/2017/">2017技术成长之路</a>
      </li>
    
      <li class="post">
        <a href="/blog/2017/02/17/virtualfunctionandvariadicparametertemplate/">虚函数和变长参数模板的妙用</a>
      </li>
    
      <li class="post">
        <a href="/blog/2016/12/25/singleton/">Singleton与多线程</a>
      </li>
    
      <li class="post">
        <a href="/blog/2016/12/04/introductiontohazardpointer/">Lock Free中的Hazard Pointer(下)</a>
      </li>
    
      <li class="post">
        <a href="/blog/2016/12/03/gccandperfopt/">性能优化的那些传说和迷思</a>
      </li>
    
  </ul>
</section>
<section>
  <h1>Friends' Link</h1>
  <ul>
    <li>
	  <li><a href="http://www.chongh.wiki/">Diting0x</a></li>
	  <li><a href="http://www.xiaolili.net/">wangli</a></li>
	  <li><a href="http://www.skykewei.top">dukewei</a></li>
	  <li><a href="http://irwenqiang.github.io">chenwenqiang</a></li>
      <li><a href="http://www.armsword.com">duruofei</a></li>
    </li>
  </ul>
</section><section>
  <h1>Yebangyu</h1>
  <p>福建人。热爱历史、K歌、NBA</p>
  <p>帝都码农</p>
  <p>历史学家，专治秦汉史</p>
</section>
<section>
 <h1>Categories</h1>
 <ul id="categories">
  <li class='category'><a href='/blog/categories/c-plus-plus/'>c++ (11)</a></li>
<li class='category'><a href='/blog/categories/soupen/'>soupen (4)</a></li>
<li class='category'><a href='/blog/categories/web/'>web (1)</a></li>
<li class='category'><a href='/blog/categories/qi-ta/'>其他 (5)</a></li>
<li class='category'><a href='/blog/categories/li-shi/'>历史 (2)</a></li>
<li class='category'><a href='/blog/categories/bing-xing-bian-cheng/'>并行编程 (20)</a></li>
<li class='category'><a href='/blog/categories/xing-neng-you-hua/'>性能优化 (2)</a></li>
<li class='category'><a href='/blog/categories/suan-fa/'>算法 (4)</a></li>
<li class='category'><a href='/blog/categories/bian-yi-lian-jie/'>编译链接 (2)</a></li>

 </ul>
</section>




  
</aside>


    </div>
  </div>
  <footer role="contentinfo"><!-- mathjax config similar to math.stackexchange -->
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
  jax: ["input/TeX", "output/HTML-CSS"],
  tex2jax: {
    inlineMath: [ ['$', '$'] ],
    displayMath: [ ['$$', '$$']],
    processEscapes: true,
    skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
  },
  messageStyle: "none",
  "HTML-CSS": { preferredFont: "TeX", availableFonts: ["STIX","TeX"] }
});
</script>
<script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML" type="text/javascript"></script>
<p>
  Copyright &copy; 2017 - Yebangyu -
  <span class="credit">Powered by <a href="http://octopress.org">Octopress</a></span>
</p>
<script type="text/javascript">var cnzz_protocol = (("https:" == document.location.protocol) ? " https://" : " http://");document.write(unescape("%3Cspan id='cnzz_stat_icon_1257548193'%3E%3C/span%3E%3Cscript src='" + cnzz_protocol + "s11.cnzz.com/z_stat.php%3Fid%3D1257548193' type='text/javascript'%3E%3C/script%3E"));</script>

</footer>
  











</body>
</html>
